#include<iostream>
using namespace std;
#include<unordered_map>
#include<set>
#include<vector>

class Graph;
class Node;
class Edge;



class Node
{
public:
    int value; //点的名字 可以更换类型 比如改成string 可以代表 "北京"
    int in; //入度
    int out; //出度
    vector<Node*> nexts; //当前点的直接邻居 当前点发散的
    vector<Edge*> edges; //属于当前点的边
public:
    Node() {
        
    }
    Node(int value) {
        this->value = value;
        this->in = 0;
        this->out = 0;
    }
};

class Edge
{
public:
    int weight; //权值
    Node* from; //源
    Node* to; //目的
public:
    Edge(int weight,Node* from,Node* to) {
        this->weight = weight;
        this->from = from;
        this->to = to;
    }
};

class Graph
{
public:
    unordered_map<int,Node*> nodes; //点集 <编号,点>
    set<Edge*> edges; //边集 <边>
public:
    //释放申请的空间
    ~Graph() {
        //释放点空间
        for(auto it = nodes.begin(); it != nodes.end(); it++) {
            if(it->second) {
                delete(it->second);
                it->second = nullptr;
            }
        }
        //释放边空间
        for(auto it = edges.begin(); it != edges.end(); it++) {
            auto edgePtr = *it;
            if(edgePtr) {
                delete edgePtr;
                edgePtr = nullptr;
            }
        }
    }
public:
    //添加节点
    void addNode(int val) {
        auto nodes_map = this->nodes;
        if(nodes_map.find(val) == nodes_map.end()) {
            // 新点 添加进map
            // cout << "add" << val << endl;
            this->nodes.insert(pair<int,Node*>(val,new Node(val)));
        }
    }
    //添加边
    void addEdge(int from,int to,int distance) {
        if(
            this->nodes.find(from) == this->nodes.end()
            ||
            this->nodes.find(to) == this->nodes.end()
            ) {
            cout << "not find" << endl;
            exit(-1);
        }
        auto from_node = this->nodes.find(from)->second;
        auto to_node = this->nodes.find(to)->second;
        //修改from的出度 to的入度
        from_node->out++;
        to_node->in++;
        //添加from的直接邻居
        from_node->nexts.push_back(to_node);
        //构建新的边
        Edge* new_edge = new Edge(distance,from_node,to_node);
        //添加from的所属边
        from_node->edges.push_back(new_edge);
        //在图中记录该边
        this->edges.insert(new_edge);
    }
    //打印图的信息
    void showGraph() {
        cout << "点的数目:" << this->nodes.size() << endl;
        for(auto it=this->nodes.begin(); it!=this->nodes.end(); it++) {
            auto node = it->second;
            cout << "node:" << node->value << "\t"
                << "in:" << node->in << "\t"
                << "out:" << node->out << endl;
            cout << "\t邻居节点:";
            auto next = node->nexts;
            for(auto nit=next.begin(); nit!=next.end(); nit++) {
                cout << (*nit)->value << ",";
            }
            cout << "\t所属边:";
            auto edge = node->edges;
            for(auto eit=edge.begin(); eit!=edge.end(); eit++) {
                cout << "{" << (*eit)->to->value << "," << (*eit)->weight << "},";
            }
            cout << endl;
        }
        cout << "====================================" << endl;
        cout << "边的数目:" << this->edges.size() << endl;
        for(auto it=this->edges.begin(); it!=this->edges.end(); it++) {
            cout << "\tfrom:" << (*it)->from->value << " to:" << (*it)->to->value << " weight:" << (*it)->weight << endl;
        }
    }
};